package cn.camel.algorithm.tree.disjoint_set;

import lombok.Data;

/**
 * @author: Camel
 * @description: 自定义并查集实现
 * @date: 2025/10/19 17:59
 */
@Data
public class DisjointSet {
    private int[] parent; // 父节点数组
    private int[] rank; // 树的高度
    private int count; // 连通分量数量

    public DisjointSet(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    // 查找（路径压缩）
    public int find(int x) {
        if(x < 0 || x >= parent.length) throw new IllegalArgumentException("索引不在范围内");
        if(parent[x] != x){
            parent[x] = find(parent[x]); // 路径压缩
        }
        return parent[x];
    }

    // 合并(按秩合并)
    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if(rootX == rootY) return; // 已经在同一集合
        if(rank[rootX] < rank[rootY]){
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        }else{
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count --; // 连通分量减少
    }

    public boolean isConnected(int x, int y) {
        return find(x) == find(y);
    }

}
